一文读懂细胞自动机的起源、原理和应用
全文共4760字，预计学习时长9分钟
细胞自动机是一种非常简单的计算形式，它的起源很难确定，但早在20世纪50年代初，洛斯阿拉莫斯的数学家斯坦尼斯劳·乌兰姆就用第一台数字计算机来处理过随时间演化的图案。他称之为“递归定义的几何学”。
第一个真正的细胞自动机可能是由乌兰姆的密友，著名的数学家和计算机科学家约翰尼·冯·诺依曼发明的。乌兰姆建议冯·诺依曼尝试在人工宇宙中构建基于规则的机器，这有助于模拟自我复制。冯·诺依曼选择了一个棋盘宇宙，其中每个方块代表一个遵守一套规则的细胞。这就是第一个细胞自动机。
细胞自动机是一种非常简单的计算形式。当你观察周围的世界时，你所看到的事物是处于一定的位置和状态的。生物细胞位于其他细胞丛中的特定位置，其状态要么是活着的，要么是死亡的。你可以想出其他非生物学的例子，但正是这一生物学例子真正推动了细胞自动机的诞生。
假设我们有一个细胞，它有特定的位置和状态。那么，影响细胞状态的因素是什么？
在大多数情况下，你会假设细胞的状态受其周围细胞的影响。然而重点是在没有细胞的几英里外发生了什么。这是一种局部化假设，也是大多数经典物理学固有的假设。例如，波是由一个微分方程描述的，此微分方程将一个点上发生的事情与该点周围无穷小的区域中发生的事情联系起来。
你或许会认为局部假设过于严格，因为它不允许远程交互，但在物理世界中，远程交互是通过点对点移动的影响而产生的。远程交互是通过只依赖于局部相互作用的脉冲和波的传播产生的。
我们最终假设影响细胞自动机的因素是环境。假设细胞的状态仅受当地环境的影响。然而在大多数情况下，我们会将假设范围缩到更小，认为细胞的状态只受其当前状态和相邻细胞状态的影响。
根据此想法，假设最开始你有一个初始的细胞群，且每个细胞都有一个初始状态，然后你让这个细胞群进行分裂。此操作通常要在几段不同时间内完成——你也可以在连续时间内运行细胞自动机，但这样操作起来难度更大。
当时间为t时，你获得了所有细胞的位置和状态；然后运用规则，根据每个细胞的当前状态和相邻细胞的状态推测出此细胞的状态。当时间为t+1时，所有细胞都能按照相同的规则改变其状态。
要明确定义细胞自动机，必须确定细胞可能的状态、细胞的初始排列情况和更新规则。那么你希望这种计算可以用来做什么呢？
你可以将细胞自动机视为用于描述许多物理现象的经典微分方程的数字版本。 但是，细胞自动机并不像你认为的那样容易分析。典型的细胞自动机中使用的规则的性质使得我们很难预测在任意给定的初始条件下细胞将发生什么变化。
例如，你可能会问，给定的一组细胞是否会振荡、消失或无约束地生长，但很难得出问题的答案。细胞自动机之所以吸引人，是因为它们不可预测，而且大多无法测量。
细胞自动机是本地规则如何影响全局组织行为的例子，或者至少是看起来像全局组织行为的例子。
能够识别轮廓的细胞自动机
我们用一个矩形网状细胞群作为执行某些有用操作的细胞自动机示例，其中每个细胞都为黑色或白色并处于初始设置状态：
每个细胞在下一个步骤都将遵守如下规则：
如果一个细胞为黑色，与之相邻的细胞为白色，那么此细胞将保持黑色，反之，细胞将变为白色。
这里，相邻细胞指的是水平或垂直相邻的任何细胞。
你认为这个所有细胞都遵守的简单规则将导致怎样的结果？
你或许会感到惊讶，此规则仅将原始形状的轮廓保留为黑色：
换句话说，此规则成功地筛选出了形状的轮廓。请注意，任何细胞都只使用了本地信息，但却成功地提取了我们可能认为是全局的东西，即轮廓。
这种现象与在体育赛事中人群中的成员被要求在特定时间举起带有不同的图片和图案的卡片的情况相同。
应用本地规则可以产生全局模式。
约翰康威的细胞自动机Life
我们举的例子非常简单且深入人心，对于细胞自动机来说非常容易理解。在所有细胞自动机中，最著名的是康威的生命游戏（Conway's Life），这看起来同样很简单，但是我们花了很长时间才弄清楚它的工作方式，而且我们还在继续探寻中。
此细胞自动机是由剑桥数学家约翰·霍顿·康威（John Horton Conway）于1970年设计的，并在马丁·加德纳（Martin Gardner）的《科学美国人》专栏（1970年10月和1971年2月）公开了此设计。
Life中的规则很简单。即宇宙是一个矩形网格，每个网格方格代表一个细胞，它可以是活的也可以是死的。
每个细胞显然有八个相邻细胞，每一代细胞的情况取决于与之相邻细胞的数目：
N Next generation2 No change3 Alive or On0,1,4-8 Dead or off
请注意，此规则非常简单。想象如果你是一个巨大矩形细胞中间的细胞，你就知道你该做什么了。你只需计算与你相邻的八个细胞中有多少是活着的，如果结果为3，则将你的状态设置为“开启”（无论当前你是开启还是关闭状态）。如果计算结果正好是2，那么你将不对当前状态进行更改，而对于任何其他值，你都需要把状态设置为“关闭”。
你可以看到，Life是一个完全局部的过程，因为没有一个细胞知道它周围的全局情况。你或许认为Life非常无聊，因为在里面不太可能发生大规模的结构变化——但你这个想法是错的。
例如，试着预测一行细胞会发生什么变化——先看一个细胞，然后两个，然后三个，以此类推。
刚开始只有一个细胞死亡。
又有两个细胞在第一步死亡了，然而，这三个细胞发生了显著的变化，给出了第一个提示，表示这里正在发生很多事情。水平排列的三个细胞在下一代中变为垂直排列的细胞，然后又变回水平排列的三个细胞。振荡器就这样产生了！
四个细胞组成一个实心块，然后变成一个有孔的块，这个孔是稳定且不变的。
五个细胞经历一系列变化后会产生一组四个3细胞振荡器。
六个细胞经历一系列有趣的形状变化后消失了。
到现在为止，你可能已经明白了其中的规则。
Life是不可预测的！
了解glider
事实上，Life让人难以理解，即使是关于它简单的问题我们也很难回答。例如，是否存在能够无穷无尽地增长的模式？1969年，康威发现了一种由五个细胞组成的有趣的小模式，他称之为滑翔机（glider）。
有趣的是，滑翔机在穿过Life时，它表现得像一个可以用来建造其他形状的基本粒子一样。
然而，真正的突破是在1970年，当时，为了赢得50美元的奖金，比尔·戈斯珀发现了滑翔机枪。
这种排列复杂的细胞每30代就会发射一次新的滑翔机。最后，实验证明有些模式可以无限制地增长，因为滑翔枪每隔30代增加五个细胞。
然而，更重要的是，有了滑翔机枪，你就可以开始在Life中制造机器了！
滑翔机的气流可以像电流一样使用，因此可以被用来建立逻辑门和存储器。很快，一台完整的生命计算机就被建造出来了，证明了仅涉及每个细胞局部行为的简单规则产生了像数字计算机一样复杂的东西。换句话说，它相当于一个通用图灵机，可以计算任何可以被计算的东西。
继滑翔机枪之后，人们陆续发现了各种有趣的东西——振荡器，移动器，发射器等等。
最重要的是，即使在今天，关于Life的实验仍然还在进行；这些实验很少得到理论上的验证，即使有，也是极少数的。更重要的是，Life只是一系列类似的细胞自动机的一个例子——每一个细胞自动机都是一个简单规则的集合，它们总能导致复杂的行为。
通常，细胞自动机是一个细胞的世界，每个细胞可以处于多个状态中的一种，并且添加了一组仅依赖于相邻细胞的规则。
鉴于这些细胞自动机是小型人造宇宙，你可以看到我们并不能对它们进行很好的解释。在我们自己制造的宇宙中，我们推测每件事都可能建立在一些简单的规则之上，这些规则产生了所有的复杂行为，因此我们会去寻找大的统一理论或任何事物都适用的理论。如果我们在知道规则的情况下却找不到一个通用理论，那么结果就不尽人意了！
世界上有很多2D细胞自动机，实际上，Life只是一组名为“Totalistic”的细胞自动机的一个例子。在全局细胞自动机中，细胞相当于一个整数，数值仅取决于其相邻细胞的状态和其可能出现的当前状态的总和。
一维
如上面描述的Life一样，二维细胞自动机太复杂，因而无法详细分析。
数学家斯蒂芬·沃尔夫拉姆 提出了解决方案，他对该理论的第一个重要贡献是将情况降低到可以分析的程度。他认为一维细胞自动机值得研究。
一维细胞自动机的概念与二维细胞自动机没有什么不同，但是当我们从一行细胞开始，在下一个标有记号的地方时，该行就会被一个遵循一定规则的新行替换。
因为这只是一个一维图，因此我们实际上不需要替换现有的行，只需在其下面显示新行，建立一个完整的细胞自动机开发模式。我们还可以根据细胞的颜色、与之相邻的其他两个细胞以及它下面新细胞的颜色来指定规则。
例如，模式：
指定一个规则，如果某个细胞为白色且与之相邻的细胞中有两个为黑色，则此细胞下面的细胞也应为黑色。
由于相邻细胞只有八种可能的情况，我们只需要列出八个中每一个细胞是黑色还是白色，一个完整的规则就可以确定在任何情况下细胞可能出现的情况。
通过将黑色设为1，白色设为0，你可以为每个相邻模式标记从0到7之间的数字，然后将下一行的黑色或白色细胞看作八个0或八个1读取，即二进制数。 这可以用作指定规则的索引。
这意味着你可以按编号引用一维细胞自动机中可能的256条规则中的任何一条。 这本身就是一个概念上的突破，因为现在你可以对每条可能规则的行为进行分类。
这正是生物学家在遇到新生物圈时会做的事情。一旦你对所看到的内容进行分类，你就可以掌握其中的模式并对看到的内容进行理论分析。
如果你没有对其进行分类，无论它有多么有趣，你看到的只是一个没有任何差别的混乱行为。
沃尔夫拉姆通过模拟这些行为来检查所有256条规则，并发现有四类行为。
· 第一类行为很无聊，只会导致打开或关闭状态。
· 第二类行为也相当无聊，此类行为会导致稳定状态，比第一类稍微有趣一点。
· 第三类行为是无序行为——随机三角形和“视频噪声”。
· 最后，第四类行为产生包含“类似Life”模式的复杂行为。第四类行为表明，即使是1d 细胞自动机也有足够的复杂性来产生有趣的行为。
在这些1d 细胞自动机中，很多都产生了有趣的模式，这些模式玩起来也很有趣。从图形的角度看，这些模式或许没有分形图那样令人印象深刻，但考虑到你投入的数量，你似乎还是有所收获——这也是最重要的一点！
即使是1d 细胞自动机也足够复杂，使你相信简单中也能产生复杂的事物。实际上，规则30被提议作为一种加密方法。单向函数只是初始状态演化而来的——由于很难从最终配置反向工作到创建它的初始配置，因此信息不能被破解。
广义细胞自动机
你可以创建自己的细胞自动机类型——你可以改变网格的形式、细胞的状态以及应用的规则。如果你愿意的话，你也可以在2D以上的空间工作，但事实证明这比你想象的要困难得多。
同样令人感兴趣的是概率细胞自动机，其中的更新规则指定状态更改的概率。
有一类重要的细胞自动机是可逆的。如果初始配置和最终配置之间存在一对一的对应关系，那么在某种意义上，这样的细胞自动机是不可逆的，通常用于物理系统建模。可逆系统遵循热力学第二定律，既不产生也不破坏信息。并不是所有的细胞自动机都是可逆的，而且许多细胞自动机只能保持在最初状态——然而，这类情况很难得到证明。
今天人们对细胞自动机的研究范围非常广泛，包括在Life中寻找有趣事物的新配置、寻找具有特定物理属性的3D 细胞自动机，以及使用遗传算法培育细胞自动机。
也许最重要的是细胞自动机是分布式并行处理模型，可能比map / reduce和Hadoop使用起来更方便。如果你觉得这一点令人惊讶，请认清一个事实，即电子表格是可编程细胞自动机，其中每个单元格都有自己的规则。具有固定规则的细胞自动机是单指令多数据（SIMD）并行性的模型。具有可变规则的细胞自动机是多指令多数据（MIMD）并行性的模型。
下一步该做什么
有太多关于细胞自动机的书、报纸和网站，很难给出一个非常完整的清单。
《一种新的科学》是关于细胞自动机的书籍中最著名的，它提出了细胞自动机可以是任何事物的理论，但我们不因为它而忽视其他优秀书籍。
我最喜欢的一本书目前已经绝版了，但你仍然可以找到它的二手版本，这本书就是威廉·罗兹海姆的《进入复杂性实验室：混乱与复杂性于此相遇》。许多书名中带有“复杂性”、“混乱”或“人造生命”等词的热门科学书籍都值得一看。
如果你想阅读一本关于这些想法但处于更高的学术水平上的好书，请尝试路易·拉姆（Lui Lam）的：Nonlinear Physics for Beginners: Fractals, Chaos, Pattern Formation, Solitons, Cellular Automata and Complex Systems.
留言 点赞 发个朋友圈
我们一起分享AI学习与发展的干货
编译组：王玲、卢佳琦
相关链接：
https://dzone.com/articles/cellular-automata-jayesh-bapu-ahire-medium
如需转载，请后台留言，遵守转载规范
推荐文章阅读
长按识别二维码可添加关注
读芯君爱你